package 暴力递归;



public class Hanoi {

    /**
     * n层汉诺塔，打印步骤 2^n  - 1
     * @param n
     */
    public static void hanoi1(int n) {
        leftToRight(n);
    }

    // 请把 1~N 层圆盘 从左 到 右
    public static void leftToRight(int n) {
        if (n == 1) {
            System.out.println("Move 1 from left to right");
            return;
        }
        leftToMid(n - 1);
        System.out.println("Move " + n + "from left to right");   // 把第N层圆盘移到最右
        midToRight(n - 1);
    }

    // 从左到中
    public static void leftToMid(int n) {
        if (n == 1) {
            System.out.println("Move 1 from left to mid");
            return;
        }
        leftToRight(n - 1);
        System.out.println("Move " + n + " from left to mid");
        rightTOMid(n - 1);
    }

    // 从右到中
    public static void rightTOMid(int n) {
        if (n == 1) {
            System.out.println("Move 1 from right to mid");
            return;
        }
        rightTOLeft(n - 1);
        System.out.println("Move " + n + " from right to mid");
        leftToMid(n - 1);
    }

    // 从右到左
    public static void rightTOLeft(int n) {
        if (n == 1) {
            System.out.println("Move 1 from right to left");
            return;
        }
        rightTOMid(n - 1);
        System.out.println("Move " + n + " from right to left");
        midToLeft(n - 1);
    }

    public static void midToLeft(int n) {
        if (n == 1) {
            System.out.println("Move 1 from mid to left");
            return;
        }
        midToRight(n - 1);
        System.out.println("Move " + n + " from mid to left");
        rightTOLeft(n - 1);
    }

    public static void midToRight(int n) {
        if (n == 1) {
            System.out.println("Move 1 from mid to right");
            return;
        }
        midToLeft(n - 1);
        System.out.println("Move " + n + " from mid to right");
        leftToRight(n - 1);
    }


    // 1-N  在:from
    //      去：to
    //   另一个：other
    public static void func(int N, String from, String to ,String other){
        if (N ==1){
            System.out.println("Move 1 from " + from + " to" + to);
        }else {
            func(N-1,from,other,to);
            System.out.println("Move " + N + " from" + from +"to " + to);
            func(N-1,other,to,from);
        }
    }
    public static void hanoi2(int n){
        if (n > 0){
            func(n,"left","right","mid");
        }
    }







}
